This invention relates to a method for determining the identities of points received by the receiver section of a high speed modem used in data communiction. More particularly, this invention relates branch metric algorithms for determining the distances between signals representing eight-dimensional points and each of a plurality of eight-dimensional subconstellations.
It has been well known in the art for some time to utilize limited frequency band channels for the transmission of data over telephone voice lines. Recently, the technology has advanced to the point where transmission of data at 14,000 and even 19,200 bits of data per second is accomplishable. In providing such high data rates it has been necessary to increase the number of points in a transmitted constellation which maintaining the same maximum average power. However, because such an increase in the number of constellation points with an identical power is accompanied by the necessity that the points become closer to one another, it has likewise become necessary to separate the constellation into subconstellations where each point of a particular subconstellation is a greater distance apart from another point in that subconstellation than from other points in other subconstellations. Such an arrangement is preferred for accomplishing the trellis encoding of the transmitted points. Trellis encoding provides redundant data bits which are used to correct errors in the received signals and hence provide a gain in the signal to noise ratio of the received data signals.
Branch metric algorithms for calculating the branch metric corresponding to each point of a signal are known in the art. An example of a branch metric algorithm for a constellation with two-dimensional points may be seen with reference to U.S. Pat. No. 4,709,377 to Martinez et al. A branch metric algorithm for an eight-dimensional constellation having sixteen subconstellations of eight-dimensional points (i.e. four planes of two-dimensional points) is also known and comprises: for each received two-dimensional coordinate of an eight-dimensional vector, determining the distances between the received coordinate and a set of points in a two-dimensional plane, and between the received coordinate and non-overlapping sets of points generated by ninety, one hundred eighty and two hundred seventy degree rotations of the first set of points as inputs; providing sixteen non-overlapping subconstellations each represented by a collection of sixteen representational four-coordinate vectors, wherein the i'th coordinate of the four-coordinate representational vector represents one of said four non-overlapping sets of points in the i'th plane; for each collection of sixteen representational vectors, finding the distance between the received four-coordinate vector and the set of vectors represented by the collection of the sixteen representational four-coordinate vectors; and for each subconstellation represented by a collection of sixteen representational vectors, comparing among the distances between the received vector and each of the vectors represented by the representational vectors to find for that collection the representational vector that represents a vector having the shortest distance to the received vector. With the known branch metric algorithm having sixteen subconstellations each represented by sixteen representational vectors, a total of two hundred and forty comparisons (fifteen comparisons times the sixteen subconstellations) must be made to find the distance between the received vector and each of the sixteen subconstellations.
While the branch metric algorithm requiring two hundred and forty comparisons will provide desired results, it should be appreciated that considerable processing power must be provided to accomplish the comparisons in an extremely quick fashion for high speed modems. In fact, unless numerous processors or a dedicated especially arranged digital signal processor were provided, such a task would appear impossible. However, it will also be appreciated that the use of multiple processors, or the development of a special digital signal processor for accomplishing the comparison task are both undesirable.